package com.example.demo.sf;


import java.util.Arrays;

public class Factorial {

    public static void main(String[] args) {
//        System.out.println(factorial(5));
//        revertString(0, "abcdefg");
        // 测试 binarySearch
//        System.out.println(binarySearch(new int[]{1,2,3,4,5,6,7,8,9,10},0,9,5));
        //测试冒泡排序
//        int[] a = new int[]{10,3,5,1,2,4,7,6,9,8};
//        System.out.println("排序之前"+ Arrays.toString(a));
//        bubbleSort(a,10);
//        System.out.println("排序之后"+ Arrays.toString(a));

        System.out.println(fibonacci2(8));
    }

    /**
     * 递归阶乘
     */
    public static int factorial(int n) {
        if (n == 1) {
            return 1;
        }
        return n * factorial(n - 1);
    }

    /**
     * 反向打印字符串
     */
    public static void revertString(int n,String str){
        if(n == str.length()){
            return;
        }
        revertString(n+1,str);
        System.out.print(str.charAt(n));
    }
    /**
     * 递归实现二分查找
     */
    public static int binarySearch(int[] arr, int left, int right, int value) {
        if (left > right) {
            return -1;
        }
        int mid = (left + right) >>> 1;
        if (arr[mid] == value) {
            return mid;
        } else if (arr[mid] > value) {
            return binarySearch(arr, left, mid - 1, value);
        } else {
            return binarySearch(arr, mid + 1, right, value);
        }
    }
    /**
     * 递归实现冒泡排序
     */
    public static void bubbleSort(int[] arr, int n) {
        if (n <= 1) {
            return;
        }
        int x = 0;
        for (int i = 0; i < n - 1; i++) {
            if (arr[i] > arr[i + 1]) {
                int temp = arr[i];
                arr[i] = arr[i + 1];
                arr[i + 1] = temp;
                x = i;
            }
        }
        bubbleSort(arr, x);
    }

    /**
     * 斐波那契数列
     */
    public static int fibonacci(int n) {
        if (n <= 0) {
            return 0;
        }
        if (n == 1) {
            return 1;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);
    }

    /**
     * 使用缓存来优化斐波那契数列
     */
    public static int fibonacci2(int n) {
        int[] cache = new int[n + 1];
        //给数组填充为-1，因为斐波那契数列中，f(0) =0 所以得填充一个别的数来区分
        Arrays.fill(cache, -1);
        cache[0] = 0;
        cache[1] = 1;
        return fibonacci3(n, cache);

    }

    public static int fibonacci3(int n,int[] cache ) {
        if (cache[n] != -1) {
            return cache[n];
        }
        cache[n] = fibonacci3(n - 1,cache) + fibonacci3(n - 2,cache);
        return cache[n];
    }



}
